package com.xj.algorithm.leetcode;

/**
 * 加一
 */
public class L66_数组格式的数字加一 {

    /**
     *给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
     *
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     *
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     *
     * 示例 1:
     * 输入: [1,2,3]
     * 输出: [1,2,4]
     * 解释: 输入数组表示数字 123。
     *
     * 示例 2:
     * 输入: [4,3,2,1]
     * 输出: [4,3,2,2]
     * 解释: 输入数组表示数字 4321。
     */

    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3};
        int[] res=plusOneGood(arr);
        System.out.print("[");
        for(int i=0;i<res.length;i++){
            System.out.print(res[i]);
            if(i!=res.length-1){
                System.out.print(",");
            }
        }
        System.out.println("]");

        int[] arr2=new int[]{4,3,2,1};
        int[] res2=plusOneGood(arr2);
        System.out.print("[");
        for(int i=0;i<res2.length;i++){
            System.out.print(res2[i]);
            if(i!=res2.length-1){
                System.out.print(",");
            }
        }
        System.out.println("]");
    }

    //自己的解法：准备1个新数组，防止最高位进位。从后往前加
    public static int[] plusOne(int[] digits) {
        int length=digits.length;
        int carry=0;
        for(int i=length-1;i>=0;i--){
            int value=0;
            if(i==length-1){
                value=digits[i]+1+carry;
            }else{
                value=digits[i]+carry;
            }
            carry=value/10;
            digits[i]=value%10;
        }
        if(carry>0){
            int[] result=new int[length+1];
            result[0]=carry;
            for (int i=0;i<length;i++){
                result[i+1]=digits[i];
            }
            return result;
        }
        return digits;
    }

    //精彩解法：直接考虑9+1和不是9的数+1。最快1步，最慢O(n)
    public static int[] plusOneGood(int[] digits) {
        //遇到非9+1，直接返回，遇到9+1,那就再+1重新判断一遍，因为进位只能是1
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;

            if (digits[i] != 0) return digits;
        }

        //如果上面的是99等全9数字，则只能变成100等
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }


}
